#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=500000, maxm=5000000;

int x[maxm+1], y[maxm+1], p[maxn+1], opt[maxm+1][2][2], ans[maxm+1];
bool ele[maxn+1];

int main() {
    freopen("network.in", "r", stdin);
    freopen("network.out", "w", stdout);

    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=1; i<n; i+=2) p[i] = i+1, p[i+1]=i;
    if (n%2) p[n] = n;
    for (int i=1; i<=m; i++) scanf("%d %d", x+i, y+i);

    for (int i=1; i<=m; i++) {
        int nx=x[i], ny=y[i];
        if (p[ny]==ny) swap(nx, ny);
        if (p[nx]==nx) {
            opt[i][0][0]=opt[i][0][1]=nx;
            opt[i][1][0]=ny, opt[i][1][1]=p[ny];

            p[p[ny]]=p[ny];
            p[nx]=ny, p[ny]=nx;
        } else {
            opt[i][0][0]=nx, opt[i][0][1]=p[nx];
            opt[i][1][0]=ny, opt[i][1][1]=p[ny];

            p[p[ny]]=p[nx], p[p[nx]]=p[ny];
            p[ny]=nx, p[nx]=ny;
        }
    }

    for (int i=1; i<=n; i++) {
        if (!ele[p[i]]) ele[i]=true;
    }

    for (int i=m; i>0; i--) {
        if (opt[i][0][0]==opt[i][0][1]) {
            if (opt[i][0][0]==x[i]) {
                if (!ele[x[i]]) {
                    ans[i]=1;
                    ele[x[i]] = true;
                    ele[y[i]] = false;
                } else ans[i]=0;
            } else {
                if (!ele[y[i]]) {
                    ans[i]=0;
                    ele[y[i]] = true;
                    ele[x[i]] = false;
                } else ans[i]=1;
            }
        } else {
            if (ele[x[i]]) {
                ans[i]=0;
                if (!ele[opt[i][1][1]]) {
                    ele[y[i]] = true;
                    ele[x[i]] = false;
                }
            } else {
                ans[i]=1;
                if (!ele[opt[i][0][1]]) {
                    ele[x[i]] = true;
                    ele[y[i]] = false;
                }
            }
        }
        for (int j=0; j<2; j++) {
            p[opt[i][j][0]]=opt[i][j][1];
            p[opt[i][j][1]]=opt[i][j][0];
        }
    }

    printf("YES\n");
    for (int i=1; i<=m; i++) printf("%d", ans[i]);
    printf("\n");

    fclose(stdin);
    fclose(stdout);
    return 0;
}
